#include <time.h>
#include <string>
#include <string.h>
#include <iostream>
#include <fstream>
#include <map>
#include <stdlib.h>
#include <sstream>
#include "mpi.h"

using namespace std;

/* geracao de palavras aleatorias, letra por letra */
void gerarPalavra(char *c){


	#pragma omp parallel
	{
		int i;

		#pragma omp for
		for(i = 0; i < 5; ++i)
			c[i] = (rand() % 26) + 97;

		c[5] = '\0';
	}

}

int main(int argc, char **argv){

	/* rank do no */
	int rank;

	/* variaveis para a iteracao */
	int i, j;

	/* tamanhos a serem utilizados */
	int size, sizeMap;

	/* quantidade de elementos apagados por no e global */
	int apagados, apagadosGlobal;

	/* quantidade de nos */
	int nos;

	/* marcos de tempo */
	time_t inicio, fim, tempo;

	/* marcos de porcentagem 10, 20, 30.... */
	int marcos[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

	map<string, int> *palavras;

	/* quantidade de palavras encontradas por no */
	#pragma omp parallel 
	{
		#pragma omp sections
		{
			#pragma omp section
			{apagados = 0;}

			/* quantidade de palavras encontradas global */
			#pragma omp section
			{apagadosGlobal = 0;}

			/* map para guardar palavras lidas do arquivo */
			#pragma omp section
			{palavras = new map<string, int>();}
		}
	}

	MPI_Init(&argc, &argv);

	srand(time(NULL));

	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	/* o no mestre abre o arquivo, popula e mapa, divide e envia para os escravos */
	if(rank == 0){

		/* comeca a contar o tempo */
		time(&inicio);

		/* abrindo o arquivo */
		ifstream ifp;
		ifp.open("palavras.txt");

		/* variavel para guardar as palavras lidas */
		string output;

		string *p = new string; /* string  */
		string tokenv, tokent; /* tokens para split por virgula e tracos */

		/* enquanto o arquivo tiver palavras, ler e colocar no map */
		if(ifp.is_open()){

			while(!ifp.eof()){

				/* ler, tokenizar e adicionar ao map */
				ifp >> output;

				istringstream ss(output);

				/* split por virgula */
				while(getline(ss, tokenv, ',')) {

					istringstream is(tokenv);

					/* split por traco (hifen) */
					while(getline(is, tokent, '-')){

						/* instanciar string e colocar no mapa */
						p->assign(tokent);
						palavras->insert(pair<string, int>(*p, 0));

					}
				}
			}
		}

		#pragma omp parallel
		{

			#pragma omp sections
			{


				#pragma omp section
				{

					/* tamanho do map original, utilizado para divisao */
					size = palavras->size();

					/* quantidade de nos */
					MPI_Comm_size(MPI_COMM_WORLD, &nos);

					/* cada no tera um map com aproximadamente sizeMap palavras */
					sizeMap = size / nos;

				}

				/* enviar para todos os nos a quantidade de mensagens */
				#pragma omp section
				{MPI_Bcast(&sizeMap, 1, MPI_INT, 0, MPI_COMM_WORLD);}

				}
			}

		/* iterador usado na divisao */
		map<string, int>::iterator i1;
		i1 = palavras->begin();

		/* string que contera as keys do map a ser enviado */
		char *valor = new char[100];

		/* comprimento do valor */
		int tam;

		/* divisao do map */
		for(i = 1; i < nos; ++i){

			for(j = 0; j < sizeMap ; ++j){

				/* mandar o tam da msg, a msg e apagar do mapa completo */
				/* assim, so restarao os elementos que o no precisa eliminar */
				strcpy(valor, i1->first.c_str());
				tam = strlen(valor);
				MPI_Send(&tam, 1, MPI_INT, i, i, MPI_COMM_WORLD);
				MPI_Send(valor, strlen(valor), MPI_CHAR, i, i, MPI_COMM_WORLD);
				palavras->erase(i1);
				i1++;

			}
		}

		delete p;
		delete valor;

	}
	else{ /* o no escravo, recebe os elementos a colocar em seu mapa */

		/* quantidade de mensagens a ser recebida */
		int messages;

		/* receber a quantidade de mensagens que deve esperar */
		MPI_Bcast(&messages, 1, MPI_INT, 0, MPI_COMM_WORLD);

		/* status para o receive e variavel onde guardar */
		MPI_Status status;
		char *valor = new char[100];

		/* variavel usada para iterar */
		int i;

		/* tamanho da string a ser recebida */
		int tam;

		/* map que contera a fracao do map original correspondente a esse no */
		map<string, int> *palavras = new map<string, int>();

		/* string utilizada para insercao */
		string *p = new string;

		for(i = 0; i < messages; ++i){

			/* receber o tam da msg, a msg e colocar no mapa */
			MPI_Recv(&tam, 1, MPI_INT, 0, rank, MPI_COMM_WORLD, &status);
			MPI_Recv(valor, tam, MPI_CHAR, 0, rank, MPI_COMM_WORLD, &status);
			p->assign(valor);
			palavras->insert(pair<string, int>(*p, 0));

		}

		delete p;
		delete valor;

	}

	/* a maior palavra tem 45 caracteres, entao preciso de 9 array de 5 elementos */
	char strings[9][5];

	/* variavel que controla se o no acabou ou nao */
	int end = 0;

	/* string que concatena todos os caracteres aleatorios */
	string random;

	/* iterador usado para busca da string no map */
	map<string, int>::iterator busca;

	while(end == 0){

		#pragma omp parallel
		{


			/* gerar 9 string aleatorias */
			#pragma omp for
			for(i = 0; i < 9; ++i){

				gerarPalavra(strings[i]);

			}
		}

		/* colocar em uma string so */
		for(i = 0; i < 9; ++i){

			random.append(strings[i]);

		}

		/* ve se a string contem uma chave */
		for(busca = palavras->begin(); busca != palavras->end(); busca++){

			/* se uma chave estiver na palavra aleatoria, apagar ela do mapa */
			if(string::npos != random.find(busca->first)){

				palavras->erase(busca);
				apagados++; /* incrementar o numero de palavras encontradas */

			}

		}

		/* precisa limpar a string aleatoria */
		random.clear();

		/* se encontrou todas as palavras, fica inativo */
		if(palavras->size() == 0)
			end = 1;

		/* reducao para verificar a % de elementos encontrados */
		if(rank == 0){

			MPI_Reduce(&apagados, &apagadosGlobal, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

			/* razao entre a quantidade de elementos apagados e total inicial de elementos */
			float porcentagem = (float)apagadosGlobal / (float)size;

			/* so imprime a primeira vez que passar da porcentagem */
			for(i = 0; i < 10; ++i){

				if((porcentagem > ((i + 1) * 0.1)) && (marcos[i] == 0)){

					/* termina de contar o tempo e imprime */
					time(&fim);

					tempo = difftime(fim, inicio);

					cout << (i + 1) * 10 << "% completo em " << tempo << " segundos" << endl;
					marcos[i] = 1;

				}
			}

		}
	}

	tempo = difftime(fim, inicio);
	cout << "fim em " << tempo << " segundos" << endl;

	delete palavras;

	MPI_Finalize();

	return 0;

}
